#include"sisdRunLength.h"

void sisdRunLength(cv::Mat& _binImg, cv::Mat& _lableImg, int offset)
{
	// 连通域分析(4连通)
	// 使用游程编码算法
	// 算法步骤：
	// 1. 寻找游程
	// 2. 获取等价对
	// 3. 解决等价对

	// 前景像素: mClose(x,y) = 255
	// 背景像素: mClose(x,y) = 0

	// 检查输入图像是否为空或不是8位单通道图像
	if (_binImg.empty() || _binImg.type() != CV_8UC1)
	{
		std::cout << "RunLength 参数错误";
		return;
	}

	// 用于记录各阶段耗时
	double Time1, Time2, Time3, Time4;

	// 释放输出图像并转换为32位整型 -> 让较低的灰度值也能显示成白色，比如1和0，一个白，一个黑
	_lableImg.release();
	_binImg.convertTo(_lableImg, CV_32SC1);

	// 扩充图像边界，防止边界有前景点
	cv::copyMakeBorder(_binImg, _binImg, 1, 1, 1, 1, cv::BORDER_CONSTANT, 0);	// eg: 512 -> 514 = 512 + 2
	cv::copyMakeBorder(_lableImg, _lableImg, 1, 1, 1, 1, cv::BORDER_CONSTANT, 0);

	Time1 = static_cast<double>(cv::getTickCount()); // 记录开始时间

	// 初始化变量
	int nRuns = 0; // 游程数量
	std::vector<int> stRun, enRun, rowRun; // 存储游程的起始列、结束列和行号

	//************* 游程获取 开始 *******************
	int rows = _binImg.rows;
	int cols = _binImg.cols;

#if 1
	// SISD
	// 遍历每一行
	for (int i = 0; i < rows; i++)
	{
		const uchar* rowData = _binImg.ptr<uchar>(i); // 获取当前行数据

		// 遍历当前行的每个像素(从第2列开始)
		for (int j = 1; j < cols; j++)
		{
			// 检测从背景到前景的过渡(游程开始)
			if (0 == rowData[j - 1] && 255 == rowData[j])  // --------------------------------modify
			{
				stRun.push_back(j);   // 记录起始列
				rowRun.push_back(i);  // 记录行号
			}
			// 检测从前景到背景的过渡(游程结束)
			else if (255 == rowData[j - 1] && 0 == rowData[j])	// --------------------------------modify
			{
				enRun.push_back(j - 1); // 记录结束列
			}
		}
	}
#endif

	nRuns = (int)stRun.size(); // 获取游程总数
	// 输出游程信息
	//std::cout << "nRuns: " << nRuns << std::endl;
	//std::cout << "stRun_size: " << stRun.size() << std::endl;
	//std::cout << "enRun_size: " << enRun.size() << std::endl;
	//************ 游程获取 结束 *********************

	Time2 = (double)cv::getTickCount(); // 记录游程获取结束时间

	//************ 等价对获取 开始 ********************
	std::vector<int> runLabels; // 存储每个游程的标签
	std::vector<std::pair<int, int>> equivalences; // 存储等价标签对
	runLabels.assign(nRuns, 0);  // 初始化标签数组
	int totalLables = 1;         // 下一个可用的标签号
	int rowCur = 0;              // 当前行号
	int currRowStIdx = 0;        // 当前行的第一个游程索引
	int prevRowStIdx = -1;       // 上一行的第一个游程索引

	for (int i = 0; i < nRuns; i++)  // 遍历每个游程
	{
		if (rowRun[i] != rowCur)     // 如果切换到新的一行
		{
			rowCur = rowRun[i];      // 更新当前行号
			prevRowStIdx = currRowStIdx;  // 保存上一行的起始索引
			currRowStIdx = i;        // 设置当前行的起始索引
		}

		// 检查与上一行所有游程的连接关系
		for (int j = prevRowStIdx; j < currRowStIdx; j++)
		{
			if (stRun[i] <= enRun[j] + offset &&
				enRun[i] >= stRun[j] - offset &&
				rowRun[i] == rowRun[j] + 1)
			{
				if (runLabels[i] == 0)
					runLabels[i] = runLabels[j];
				else if (runLabels[i] != runLabels[j]) {
					equivalences.push_back(std::make_pair(runLabels[i], runLabels[j]));
				}
			}
		}

		if (runLabels[i] == 0)
			runLabels[i] = totalLables++;
	}

	totalLables--; // 调整标签总数

	// 输出标签信息
	//std::cout << "totalLables : " << totalLables << std::endl;
	//std::cout << "runLables的大小：" << runLabels.size() << std::endl;
	//************ 等价对获取 结束 ********************

	Time3 = (double)cv::getTickCount(); // 记录等价对获取结束时间

	//************ 等价对求解 开始 ********************
	// 创建等价表，初始值为false，eg: 1，2，3，4，等价表为：4x4
	std::vector<std::vector<bool>> eqTab(totalLables, std::vector<bool>(totalLables, false));
#if 1
	// 填充等价表
	std::vector<std::pair<int, int>>::iterator eqPairIt = equivalences.begin();
	int rowIdx, colIdx;
	while (eqPairIt != equivalences.end())
	{
		rowIdx = eqPairIt->first - 1;
		colIdx = eqPairIt->second - 1;
		eqTab[rowIdx][colIdx] = true;					// ------------------------------------------TODO
		eqTab[colIdx][rowIdx] = true;
		eqPairIt++;
	}
#endif
#if 0
	for (const auto& eqPair : equivalences) {
		int rowIdx = eqPair.first - 1;
		int colIdx = eqPair.second - 1;
		eqTab[rowIdx][colIdx] = true;
		eqTab[colIdx][rowIdx] = true;
	}
#endif
	//-------------------------------------------------------------

	// 使用深度优先搜索解决等价关系
	std::vector<int> labelFlag(totalLables, 0); // 标记已处理的标签
	std::vector<std::vector<int>> equaList; // 存储等价类
	std::vector<int> tempList; // 临时存储当前等价类

	for (int i = 1; i <= totalLables; i++)
	{
		if (labelFlag[i - 1]) // 如果标签已处理则跳过
			continue;

		labelFlag[i - 1] = (int)equaList.size() + 1; // 标记当前标签
		tempList.push_back(i); // 将当前标签加入临时列表

		// 深度优先搜索处理等价类
		for (size_t j = 0; j < tempList.size(); j++)
		{
			for (size_t k = 0; k < totalLables; k++)
			{
				// 如果两个标签等价且未处理
				if (eqTab[tempList[j] - 1][k] && !labelFlag[k])
				{
					tempList.push_back(k + 1); // 加入临时列表
					labelFlag[k] = (int)equaList.size() + 1; // 标记为已处理
				}
			}
		}

		equaList.push_back(tempList); // 将当前等价类加入结果
		tempList.clear(); // 清空临时列表
	}

	std::cout << "RunLength连通域个数：" << equaList.size() << std::endl;
#if 1
	// 更新标签图像
	for (std::vector<int>::size_type i = 0; i < runLabels.size(); i++)
	{
		//int label = labelFlag[runLabels[i] - 1] + 1; // 获取最终标签
		int label = labelFlag[runLabels[i] - 1]; // 获取最终标签

		// 获取当前游程在标签图像中的起始位置
		int* pData = &_lableImg.ptr<int>(rowRun[i])[stRun[i]];

		// 用最终标签填充整个游程
		for (int j = enRun[i] - stRun[i] + 1; j > 0; j--)
		{
			*pData = label;
			pData++;
		}
	}
#endif
	//************ 等价对求解 结束 ********************

	Time4 = (double)cv::getTickCount(); // 记录结束时间

	// 输出各阶段耗时占比和总耗时
	std::cout << "游程获取消耗时间：\t" << (Time2 - Time1) / (Time4 - Time1) * 100 << "%" << std::endl;
	std::cout << "等价对获取消耗时间：\t" << (Time3 - Time2) / (Time4 - Time1) * 100 << "%" << std::endl;
	std::cout << "等价对求解消耗时间：\t" << (Time4 - Time3) / (Time4 - Time1) * 100 << "%" << std::endl;
	std::cout << "总共花费时间：\t\t" << (Time4 - Time1) / cv::getTickFrequency() * 1000 << "ms" << std::endl;
}
